1. Field of the Invention
The present invention is generally related to full text document searching and retrieval, as may be performed over local and wide-area networks, and in particular to a method of performing effective document searches over multiple, independent document collections
2. Description of the Related Art
During the past few years, the quantity and diversity of information and services available over the public (Internet-type) and private (Intranet-type) local and wide area networks, generically referred to as the "Internet," has grown substantially. In particular, the variety of information accessible through such Internet based services is growing rapidly both in terms of scope and depth.
One of the significant benefits of information being accessible over the Internet is that very diverse information can be accessed in a largely presentation independent form. A number of independent Internet search services exist to provide context based, content derived indexes searchable over the Internet through a query based interface. Consequently, much if not all of the diverse information available through the Internet can be found and utilized by individuals and companies, or simply "users," who use the Internet.
While access to much of the information available through the Internet is free for public use, numerous proprietary or fee-based access document collections exist. Although such private document collections may all be accessible through the Internet, which is increasingly preferred over the many existing proprietary modem networks, the collections are generally forced to be accessible as discrete entities in order to maintain fee-based access control. In effect, such private document collections are restricted to use on a collection access for fee basis.
Private document collections are likely to continue to exist as significant sources of unique information. Independent content creators and providers derive significant revenues from the licensing of private collection content typically to collection access providers who, in turn, derive revenue from fee-based access by users to various available combinations of private collections.
In order to maximize the desirability for users to access a particular private collection and preferably related sets of private collections, a collection access provider will acquire licensed rights to make available a wide variety of individual collections of content related documents as discrete databases that can be manually selected for search by a user. Typically, searches and retrievals of information from the discrete databases are subject to specific access fees determined based on the relative commercial worth of the information maintained in the individual databases. Consequently, access fees are typically calculated on the number of documents that are variously searched, reviewed, and retrieved in preparation of a search report from a particular database.
A known problem in providing access to multiple databases is the relative difficulty or inefficiency in identifying an optimal database or set of databases that should be searched to obtain the best search report for some particular unstructured, or ad hoc, database query. In order to support even the possibility of ad hoc queries, the database search must be conducted on a full text or content established basis. Existing full text search engines typically allow a user to search many databases simultaneously. For example, commercial private collection access providers, such as Dialog.TM., allow a user to search some 500 or more different databases either individually or in manually selected sets. Consequently, the selection of the most appropriate set of databases to search places a substantial burden on the user for each query. The user must manually determine and select a particular set of databases that must, by definition, contain the desired results to a query. Such a database set selection is difficult since the selection is made preemptively and independent of the query. This burden may be even more of an issue where access fees are charged for conducting a search against a database even where no search responsive documents are found or examined. In the aggregate, this problem is typically referred to as the "collection selection problem."
The collection selection problem is complicated further when the opportunity and desire exists to search any combination of public and private document collections. The Internet effectively provides the opportunity to access many quite disparately located and maintained databases. The importance of solving the selection collection problem thus derives from the user's desire to ensure that, for a given ad hoc query, the best and most comprehensive set of possible documents will be returned for examination and potential use at minimum cost.
The collection selection problem is formidable even when dealing with a single collection provider. Dialog.TM., an exemplary collection access provider, alone provides access to over 500 separate databases, many with indistinct summary statements of scope and overlapping coverage of topics. With over 50,000 databases estimated presently available on the Internet, the collection selection problem is therefore impractical to solve reliably and efficiently by a user.
Some approaches to providing automated or at least semi-automated solutions to the collection selection problem have been developed. Known techniques, such as WAIS (wide area information server), utilize a "server of servers" approach. A "master" database is created to contain documents that describe the contents of other "client" databases as may be potentially available on the Internet. A user first selects and searches the master database to identify a set of client databases that can then be searched for the best results for a given query.
In many instances, a master WAIS database is constructed and updated manually. The master database can also be generated at least semi-automatically through the use of automatons that collect information freely from the Internet. The performance of such automatons, however, is often imperfect, if not simply incorrect, in their assessments of client databases. Even at best, certain client databases, including typically private and proprietary document collections, may block access by the automatons and are thus completely unrepresented in the master database.
Even where database access can be obtained and document summaries automatically generated, the scaling of the master database becomes problematic if only due to the incomplete, summary, and mis-characterization of document summary entries in the master database. Manual intervention to prepare and improve automaton generated document summaries will enhance the usefulness of the master database. When any manual intervention is required, however, the scaling of the master database comes at least at the expense of the useful content of the master database document summary entries. With greatly increased scale, often only abbreviated document titles or small fractions of the client database documents can be collected as summaries into the master database. As scale increases, succinct manually generated summaries of client database documents become increasingly desired, if not required, to provide any adequate content for the master database document entries. Unfortunately, even at only a modest scale, a master database of manually generated or modified document summaries becomes an impracticable construct to build or maintain.
Perhaps one of the most advanced scalable approaches to constructing and using a meaningful master database is a system known as GLOSS (Glossary-of-Servers Server). An automaton is typically used to prepare a master database document for each client database that is to be included within GLOSS. Each master database document effectively stores the frequency of whatever potential query terms occur within the corresponding client collection of documents. The master database documents are then stored as the master records that collectively form the master database.
In response to a user query, GLOSS operates against the master database documents to estimate the number of relevant client collection documents that exist in the respective client collections. These relevant document estimates are determined from a calculation based on the combined query term frequencies within each of the master database documents. GLOSS then assumes that client databases ranked as having the greatest number of combined query term occurrences are the most relevant databases to then search.
Unfortunately, utilizing a relevance system based on term frequency inherently constrains the type and effectiveness of queries that can be meaningfully directed against the master database. In addition, the estimator used by GLOSS is by definition aspecific to any client document. The GLOSS system is therefore highly subject to failures to identify client databases that may contain only a relatively few instances of the query terms, yet may contain relevant documents.
Other approaches to establishing a quantitative basis for selecting client database sets includes the use of comprehensive indexing strategies, ranking systems based on training queries, expert systems using rule-based deduction methodologies, and inference networks. These approaches are used to examine knowledge base descriptions of client document collections.
Indexing and ranking systems both operate typically against the client databases directly to, in effect, create categorizations of the client databases against search term occurrences. All possible query terms are indexed in the case of comprehensive indexing, while a limited set of predefined or static query terms are used in the case of simple ranking. Indexing thus generates a master database of selectable completeness that is nonetheless useable for selecting a most likely relevant set of client databases for a particular query. Ranking also generates a master database, though based on the results of a limited set of broad test queries intended to collectively categorize subsets of the available client databases. In effect, categorization by fixed query term results in generally orthogonal lists of ranked client database sets.
Expert system approaches typically operate on client database scope and content descriptions to deduce or establish a basis for subsequently deducing a most likely set of databases that will likely contain the most relevant documents for a particular query.
Finally, inference networks utilize a term-frequency based probabilistic approach to estimating the relevance of a particular client database as against other client databases. Unfortunately, the known implementations of inference networks are unable to accurately rank the potential relevance of client databases of diverse size and differences in the generation of summaries for each of the client databases considered.
Thus, the known approaches to solving the client database collection selection problem are generally viewed as inefficient in the assembly, construction, and maintenance of a master document database. These known systems are also viewed as often ineffective in identifying the likely most relevant documents within entire sets of collections because real world collections are often highly variable in size, scope, and content or cannot be uniformly characterized by existing quantitative approaches.
Another and perhaps practically most significant limitation of these known systems is that each must be self-contained in order to operate. This is a direct result of each system utilizing a proprietary algorithm, whether implemented as a manual operation or through the operation of an automaton, to universally assemble the information necessary to create or populate the master database documents from the raw collection documents. As such, these known systems cannot depend on one-another or on any other indexing systems; each must be responsible for both the total generation and subsequent exclusive utilization of their master database summary record documents.
Consequently, there is a clear need for an enhanced system of handling the collection selection problem in view of the ever increasing number and scale of collections available on the Internet and the increasing variety of the collections, both in terms of existing organization and informational content.